package com.jiang.专题.动态规划.Q115;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/13 21:59
 */
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        // 状态方程
        // dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];  s[i] = t[j]
        // dp[i][j] = dp[i + 1][j]; s[i] != s[j]
        int[][] dp = new int[m + 1][n + 1]; // dp[i][j] 表示在s[i:m-1]子序列中t[j:n-1]的出现次数
        // 初始化
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }
        // 完善dp数组
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }
}
